package demo.DataStrucAndAlgo.AlgorithmOfTen;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/12-08-12-16:31
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen   Dijkstra算法 （迪杰斯特拉算法）
 */
/*
求某一点到其他点的最短距离
e.g.
有一个7村庄（A~G）,需要求得G村庄到其他村庄的最短距离
    A~B 5  A~C 7  A~G 2  B~D 9
    B~G 3  C~E 8  D~F 4  E~F 5
    E~G 4  F~G 6
算法流程（广度优先搜索思想）
    visited_vertex数组：存储顶点是否被访问的信息 （1被访问）
    pre_visited数组：存储对应结点的父节点
    distance数组：存储对应结点距起始结点的距离

    1、以G为初始起点，将其周围可访问且直连的顶点遍历出来，将数据用数组保存
    2、选取周围顶点中最短的顶点，将其标记为已访问，并将其周围可访问且直连的顶点遍历出来，同时寻找有无形成比之前的路径更短的路径：
    有，则更新数组；没有，则重复此步
    3、选取周围顶点中最短的顶点，将其标记为已访问，并将其周围可访问且直连的顶点遍历出来，同时寻找有无比之前的路径更短的路径：有，则更新
    数组；没有，则重复此步
    4、选取周围顶点中最短的顶点，将其标记为已访问，并将其周围可访问且直连的顶点遍历出来，同时寻找有无比之前的路径更短的路径：有，则更新
    数组；没有，则重复此步
    ...
    当所有顶点都被访问过时，迪杰斯特拉算法完成，结果就存储在数组中。

 */
public class Dijkstra {
}
